﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Data.Entity.Core.Objects;
using System.Data.Entity.Core.Metadata.Edm;

namespace DynamicFiltering
{

    public class EntityModelNavigator
    {

        private readonly List<NavigationItem> _navItems;
        private string _toEntityName;
        private string _passThroughEntityName;

        /// <summary>
        /// A "chain" is a valid path from one entity to another related entity.
        /// </summary>
        private LinkedList<NavigationItem> _chain;

        /// <summary>
        /// A true tree; the first node in every list in this list will be the same.
        /// </summary>
        private readonly List<LinkedList<NavigationItem>> _chainTree = new List<LinkedList<NavigationItem>>();

        /// <summary>
        /// The one chain of all possibles that we want to use.
        /// </summary>
        public LinkedList<NavigationItem> Chain { get { return _chain; } }

        /// <summary>
        /// This is the param that will be applied to the target entity.
        /// Referenced by LinqGenerator, stored here for convenience.
        /// </summary>
        public object ToEntityFilter { get; set; }

        public EntityModelNavigator( ObjectContext context )
        {
            _navItems = new EntityNavigationList( context ).List;
        }

        /// <summary>
        /// What's a chain?  See comment above Chain prop
        /// </summary>
        /// <param name="passThroughEntityName">Not necessary most of the time.  Needed when the *very* shortest join discovered is not the join you need.
        /// In that case, you would pass the name (typeof(MyEntity).Name) of the entity you need included in the join.</param>
        public bool BuildShortestChain( string fromEntityName, string toEntityName, string passThroughEntityName = "" )
        {
            _passThroughEntityName = passThroughEntityName;
            //var ticks = Environment.TickCount;

            var result = false;
            _toEntityName = toEntityName;
            var temp = new LinkedList<NavigationItem>();
            var fromNavigationItem = ( from n in _navItems where n.FromEntity == fromEntityName select n ).FirstOrDefault();
            if ( fromNavigationItem != null )
            {
                temp.AddLast( fromNavigationItem );
                if ( fromEntityName == toEntityName )
                {
                    SetChainForEntitySearchingForItself( temp, fromNavigationItem );
                    return true;
                }
                else
                {
                    result = BuildChainFrom( temp, fromNavigationItem, new List<NavigationItem> { fromNavigationItem } );
                    if ( result )
                    {
                        /// Optimization 1:  If there is only one possible chain, don't continue.
                        /// We now have our first possible chain between the entities.
                        /// From this chain, start building alternative paths unless it's only 2 entities long in which case we already have our shortest path.
                        if ( _navItems.Count > 2 )
                        {
                            BuildAlternativeChains();
                        }

                        /// We've (potentially) constructed many chains; now set our public Chain prop to the shortest/best.
                        SetShortestChain();
                        CorrectFirstNode();
                        AugmentMiddleChainReferences();
                    }
                }
            }

            //Console.WriteLine( "took {0} ms; {1} chains", Environment.TickCount - ticks, _chainTree.Count );
            return result;
        }

        /// <summary>
        /// If we're here, that means the request was for EntityX related to itself
        /// In this case, we're just going to make a 2 item chain that points to itself and the LinqGenerator will figure it out.
        /// </summary>
        private void SetChainForEntitySearchingForItself( LinkedList<NavigationItem> temp, NavigationItem firstNavigationItem )
        {
            firstNavigationItem.CorrespondingForwardNav = firstNavigationItem;
            temp.AddFirst( firstNavigationItem );
            _chain = temp;
        }

        /// <summary>
        /// BuildChainFrom always adds the next nav item that points back to the preceeding item (it can't be any other way).
        /// Now that we have the full chain, we will need to add in those navs that point the other way (the CorrespondingForwardNav property).
        /// LinqGenerator needs those.
        /// This applies to all "middle" nav items (excludes first and last nav nodes).
        /// </summary>
        private void AugmentMiddleChainReferences()
        {
            if ( _chain.Count > 2 )
            {
                var current = _chain.First;
                while ( current.Next != null ) // while we're still working with middle nodes
                {
                    var forwardNode = ( from n in _navItems where n.FromEntity == current.Value.FromEntity && n.ToEntity == current.Next.Value.FromEntity select n ).FirstOrDefault();
                    current.Value.CorrespondingForwardNav = forwardNode;
                    current = current.Next;
                }
            }
        }

        private void SetShortestChain()
        {
            var shortestChainList = EntityChainQuality.FindListItemsWithLowestCountOf<LinkedList<NavigationItem>>( _chainTree, ( ni ) =>
            {
                if ( string.IsNullOrEmpty( _passThroughEntityName ) )
                {
                    return ni.Count;
                }
                else
                {
                    /// See remarks above BuildShortestChain()
                    if ( ChainContainsPassThroughEntity( ni ) )
                    {
                        return ni.Count;
                    }
                    else
                    {
                        return int.MaxValue;
                    }
                }
            } );
            if ( shortestChainList.Count == 1 )
            {
                _chain = shortestChainList[0];
            }
            else
            {
                _chain = DetermineBestOfShortestChains( shortestChainList );
            }
        }

        private bool ChainContainsPassThroughEntity( LinkedList<NavigationItem> ni )
        {
            return ni.Any( n => String.Compare( n.ToEntity, _passThroughEntityName, false ) == 0 );
        }

        private LinkedList<NavigationItem> DetermineBestOfShortestChains( List<LinkedList<NavigationItem>> shortestChainList )
        {
            var entityChainAttributesList = new List<EntityChainQuality>( shortestChainList.Count );
            shortestChainList.ForEach( c => entityChainAttributesList.Add( new EntityChainQuality() { Chain = c } ) );
            InitializeQualityList( entityChainAttributesList );
            return EntityChainQuality.HighestQualityChain( entityChainAttributesList );
        }

        /// <summary>
        /// Given a list of EntityChainQuality, set each object's ZeroOrOneCount and ToEntityNameCount properties
        /// </summary>
        public void InitializeQualityList( List<EntityChainQuality> ecqList )
        {
            ecqList.ForEach( ecq =>
            {
                ecq.Chain.ToList().ForEach( c =>
                {
                    if ( c.FromEntity.Contains( _toEntityName ) )
                    {
                        ecq.ToEntityNameCount++;
                    }
                    if ( c.ToMultiplicity == RelationshipMultiplicity.ZeroOrOne )
                    {
                        ecq.ZeroOrOneCount++;
                    }
                } );
            } );
        }

        /// <summary>
        /// Pre: we've created a starting chain that is greater than 2 in length.
        /// </summary>
        private void BuildAlternativeChains()
        {
            var treeLevel = 0;
            var overallListIndex = 0;

            /// Step through the overall list of chains between entities and discover alternate chains.
            /// The overall list grows as this while loop executes.
            while ( _chainTree.Count > overallListIndex )
            {
                var currentList = _chainTree[overallListIndex];
                overallListIndex++;
                treeLevel = 1; // see param notes on TryBuildNewChain
                while ( currentList.Count > treeLevel + 1 )
                {
                    /// We have possible alternate branches from this level of the current list / tree node.
                    TryBuildNewChain( treeLevel, currentList );
                    treeLevel++;
                }
            }
        }

        /// <summary>
        /// First (parent) recursive method: child is BuildChainFrom.  If child BuildChainFrom finds a new valid chain, it will be added
        /// to _chainTree.
        /// In this method, we're building new "sub" chains, e.g., chains that build off previously built leading portions.  They're new 
        /// branches off of some level of an existing chain greater than 1 (lower down in the overall tree).
        /// </summary>
        /// <param name="treeLevel">The level on the tree we want to branch anew from in order to discover alternate valid chains.</param>
        /// <param name="currentList"></param>
        private void TryBuildNewChain( int treeLevel, LinkedList<NavigationItem> currentList )
        {
            var possibleNewChain = new LinkedList<NavigationItem>();

            /// The possible new chain will retain the same linked list of the list passed in up to the node at position tree level
            AddLeadingSectionOfLinkedListTo( currentList, possibleNewChain, treeLevel );

            /// Optimization 2:
            /// 
            /// Exclude list is the list of related entities that have branched from all lists at this same tree level.
            /// That is, if I'm at entity B and there already exists a chain that branches from this same level to entity C, I'm not going
            /// to pursue any more branches through entity C in this pass.
            /// 
            /// The effect is that some possible chains will not be covered (in order to cover all possible combinations, we would only
            /// include in the skip list those entities branched from the *current* list), but (apparently, from testing) those unfound (excluded) chains 
            /// will always be less efficient than chains already discovered.
            /// This reduces the chain count in a chain whose shortest path is 4 entities in a model with a decent amount of entities from it's 
            /// target from the hundreds to the tens.
            var excludeList = BuildExcludeList( treeLevel );
            BuildChainFrom( possibleNewChain, possibleNewChain.Last.Value, excludeList );
            //TryBuildNewChain( treeLevel, currentList );
        }

        /// <summary>
        /// See comment "Optimization 2" in TryBuildNewChain
        /// </summary>
        /// <param name="treeLevel">See notes for param on caller</param>
        private List<NavigationItem> BuildExcludeList( int treeLevel )
        {
            var result = new List<NavigationItem>();
            _chainTree.ForEach( c =>
            {
                if ( c.Count > treeLevel )
                {
                    var node = c.First;
                    result.Add( node.Value );
                    for ( int i = 0; i < treeLevel; i++ )
                    {
                        node = node.Next;
                        result.Add( node.Value );
                    }
                }
            } );
            return result;
        }

        /// <summary>
        /// Add nodes from one linked list to another such that linking pointers are set new
        /// </summary>
        private static void AddLeadingSectionOfLinkedListTo( LinkedList<NavigationItem> fromList, LinkedList<NavigationItem> toList, int count )
        {
            var node = fromList.First;
            toList.AddLast( node.Value );
            for ( int i = 1; i < count; i++ )
            {
                node = node.Next;
                toList.AddLast( node.Value );
            }
        }

        /// <summary>
        /// Main recursive method (TryBuildNewChain is also recursive).  Finds the path to the target if it exists.
        /// </summary>
        /// <param name="temp"></param>
        /// <param name="fromNavigationItem"></param>
        /// <param name="excludeList">List of navigation items to exclude from becoming the next nav item in the current chain at current tree level.</param>
        /// <returns>Whether a path was found from the current fromNavigationItem</returns>
        private bool BuildChainFrom( LinkedList<NavigationItem> temp, NavigationItem fromNavigationItem, List<NavigationItem> excludeList )
        {
            var result = false;

            if ( BetterChainExists( temp ) )
            {
                /// Optimization 3: If this wasn't here, we might build hundreds of chains of various lengths.
                return result;
            }

            var nextPossibleNavItems = ( from n in _navItems
                                         /// Exclude all previous items found or your stack cup will runneth over.
                                         /// We can't simply check the temp list objects themselves because we may find items which
                                         /// aren't in the temp list but whose "from entity" is one we've already encountered.
                                         where !excludeList.Contains( n )
                                                && ( String.Compare( n.ToEntity, fromNavigationItem.FromEntity, false ) == 0 )
                                             // Optimization 4: Null entity set indicates many to many pass through entity.  We never want that as our target.
                                                && ( n.EntitySet != null )
                                         select n ).ToList();  // Must create list; enumerable doesn't work downstream.

            excludeList.AddRange( from n in nextPossibleNavItems select n );

            /// Optimization 5: If one of our immediate navigation entities (neighbors) is the target, no need to continue.
            /// This prevents LOTS of useless chains from being created.
            result = TryDirectToTarget( temp, nextPossibleNavItems );

            /// If one of our immediate navigation entities (neighbors) is NOT the target; continue seeking...
            if ( !result )
            {
                foreach ( var nextPossibleNavItem in nextPossibleNavItems )
                {
                    temp.AddLast( nextPossibleNavItem );
                    result = BuildChainFrom( temp, nextPossibleNavItem, excludeList );
                    if ( result )
                    {
                        break;
                    }
                    else
                    {
                        temp.Remove( nextPossibleNavItem );  // unwind this mutha; it's no good.
                    }
                }
            }

            return result;
        }

        private bool BetterChainExists( LinkedList<NavigationItem> temp )
        {
            for ( int i = 0; i < _chainTree.Count; i++ )
            {
                /// If this is the first time through, there will be no chains in the main list, so this won't hit.
                if ( _chainTree[i].Count < temp.Count )
                {
                    if ( string.IsNullOrEmpty( _passThroughEntityName ) || ChainContainsPassThroughEntity( _chainTree[i] ) )
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        /// <summary>
        /// Attempt to shortcircuit other possible paths if the target is in our current list of related entities.
        /// Only here is a new chain added to _chainTree.
        /// </summary>
        private bool TryDirectToTarget( LinkedList<NavigationItem> temp, List<NavigationItem> nextPossibleNavItems )
        {
            var target = ( from n in nextPossibleNavItems where n.FromEntity == _toEntityName select n ).FirstOrDefault();
            if ( target == null )
            {
                return false;
            }
            else
            {
                temp.AddLast( target );
                _chainTree.Add( temp );  // we've completed a chain.
                return true;
            }
        }

        /// <summary>
        /// The very first nav that was created in the topmost BuildShortestChain method may or may not be pointing
        /// directly to the next node which is only discovered later.
        /// </summary>
        private void CorrectFirstNode()
        {
            if ( ( _chain != null ) && ( _chain.Count > 0 ) )
            {
                var firstNode = _chain.First.Value;
                var targetNode = _chain.First.Next.Value;
                var trueFirstNode = ( from n in _navItems where n.FromEntity == firstNode.FromEntity && n.ToEntity == targetNode.FromEntity select n ).FirstOrDefault();
                if ( trueFirstNode != null )
                {
                    _chain.RemoveFirst();
                    _chain.AddFirst( trueFirstNode );
                }
            }
        }

    }

}
